package com.leet.code.lcof;

import java.util.ArrayList;
import java.util.List;

public class Code35 {

    public static void main(String[] args) {

    }

    public Node copyRandomList(Node head) {

        if (head == null) return null;

        List<Node> root = new ArrayList<>();
        List<Node> result = new ArrayList<>();

        Node last = new Node(head.val);
        result.add(last);
        root.add(head);
        head = head.next;

        while (head != null) {
            root.add(head);
            last.next = new Node(head.val);
            last = last.next;
            result.add(last);
            head = head.next;
        }

        for (int i = 0; i < root.size(); i++) {
            Node h = root.get(i);
            Node s = result.get(i);
            if (h.random == null) {
                continue;
            }
            s.random = result.get(root.indexOf(h.random));
        }

        return result.get(0);

    }


    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
}
